﻿//二叉树里面的路径被定义为:
//从该树的任意节点出发，经过父 = > 子或者子 = > 父的连接，达到任意节点的序列。
//注意 :
//1.同一个节点在一条二叉树路径里中最多出现一次
//2.一条路径至少包含一个节点，且不一定经过根节点
//
//给定一个二叉树的根节点root，请你计算它的最大路径和



/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param root TreeNode类
         * @return int整型
         */
        int ret = -1010;
        int maxPathSum(TreeNode* root) {

            dfs(root);
            return ret;
        }
        int dfs(TreeNode* root) {
            if (root == nullptr) return 0;
            int l = max(0, dfs(root->left));// 左⼦树的最⼤单链和
            int r = max(0, dfs(root->right)); // 右⼦树的最⼤单链和
            // 经过root的最⼤路径和
            ret = max(ret, root->val + l + r);
            return root->val + max(l, r);
        }

};